//给定一个只包含数字的字符串，复原它并返回所有可能的 IP 地址格式。 
//
// 有效的 IP 地址 正好由四个整数（每个整数位于 0 到 255 之间组成，且不能含有前导 0），整数之间用 '.' 分隔。 
//
// 例如："0.1.2.201" 和 "192.168.1.1" 是 有效的 IP 地址，但是 "0.011.255.245"、"192.168.1.312"
// 和 "192.168@1.1" 是 无效的 IP 地址。 
//
// 
//
// 示例 1： 
//
// 输入：s = "25525511135"
//输出：["255.255.11.135","255.255.111.35"]
// 
//
// 示例 2： 
//
// 输入：s = "0000"
//输出：["0.0.0.0"]
// 
//
// 示例 3： 
//
// 输入：s = "1111"
//输出：["1.1.1.1"]
// 
//
// 示例 4： 
//
// 输入：s = "010010"
//输出：["0.10.0.10","0.100.1.0"]
// 
//
// 示例 5： 
//
// 输入：s = "101023"
//输出：["1.0.10.23","1.0.102.3","10.1.0.23","10.10.2.3","101.0.2.3"]
// 
//
// 
//
// 提示： 
//
// 
// 0 <= s.length <= 3000 
// s 仅由数字组成 
// 
// Related Topics 字符串 回溯算法 
// 👍 475 👎 0

package com.leetcode.editor.cn;

import java.util.ArrayList;
import java.util.List;

//Java：复原IP地址
class P93RestoreIpAddresses {
    public static void main(String[] args) {
        Solution solution = new P93RestoreIpAddresses().new Solution();
        // TO TEST
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public List<String> restoreIpAddresses(String s) {
            List<String> res = new ArrayList<>();
            if(s.length() <= 3 || s.length() > 12) {
                return res;
            }
            dfs(s, 0, 0, res, "");
            return res;
        }

        private void dfs(String s, int index, int depth, List<String> res, String cur){
            if(depth == 3){
                String tmp2 = s.substring(index, s.length());
                if(judge(tmp2))
                    res.add(cur+tmp2);
                return ;
            }

            //每次可以选1 2 3位
            for(int i = 1; i <= 3; i++){
                if(index+i >= s.length())
                    break;
                String tmp = s.substring(index, index+i);
                if(!judge(tmp))
                    continue;

                dfs(s, index+i, depth+1, res, cur+tmp+".");
            }
        }

        private boolean judge(String str){
            //长度大于3的错误
            if(str.length() > 3)
                return false;
            //0开头的错误
            if(str.length() > 1 && str.charAt(0) == '0')
                return false;
            //有特殊字符的错误
            for(int i = 0; i < str.length(); i++){
                if(str.charAt(i) > '9' || str.charAt(i) < '0')
                    return false;
            }
            //大于255的错误
            if(Integer.parseInt(str) > 255)
                return false;

            return true;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}